package leetcode_600;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeSet;

/**
 *@author 周杨
 *IPO_502 投资问题 有限的出手次数 
 *describe:用贪心算法 AC 20%
 *2018年9月5日 下午9:10:18
 */
public class IPO_502 {
	public static void main(String[] args) {
		IPO_502 test=new IPO_502();
		System.out.println(test.findMaximizedCapital1(2, 0, new int[]{1,2,3}, new int[] {0,1,1}));
	}
	
	 /**
	 * describe:双优先队列
	 * 2018年9月5日 下午9:09:28
	 */
	public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
	        PriorityQueue<int[]> pqCap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
	        PriorityQueue<int[]> pqPro = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
	        
	        for (int i = 0; i < Profits.length; i++) {
	            pqCap.add(new int[] {Capital[i], Profits[i]});
	        }
	        
	        for (int i = 0; i < k; i++) {
	            while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
	                pqPro.add(pqCap.poll());
	            }
	            
	            if (pqPro.isEmpty()) break;
	            
	            W += pqPro.poll()[1];
	        }
	        
	        return W;
	    }
	
	/**
	 * describe:不知道哪里出了问题
	 * 2018年9月5日 下午9:09:07
	 */
	public int findMaximizedCapital1(int k, int W, int[] Profits, int[] Capital) {
Comparator<Integer> com=new Comparator<Integer>() {
			
			@Override
			public int compare(Integer o1, Integer o2) {
				if(Profits[o1]>Profits[o2])
					return -1;
				else if(Profits[o1]==Profits[o2])
					if(Capital[o1]<Capital[o2])
						return -1;
					else if(Capital[o1]==Capital[o2])
						return 0;
					else
						return 1;
				else
					return 1;
			}
		}; 
		Set<Integer> set=new TreeSet<Integer>(com);
		for(int i=0;i<Profits.length;++i) {
			set.add(i);
		}
		while(k>0) {
			Integer purchase=null;
			for(Integer now:set) {
				if(W>=Capital[now]) {
					purchase=now;
					W+=Profits[now];
					break;//找到适合的
				}
			}
			--k;
			if(purchase==null) {
				return W;//没有找到
			}
			else
				set.remove(purchase);
		}
		
		return W;
    }
}
